<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <!-- 出租车的最大盈利 -->
    <script>
      var maxTaxiEarnings = function (n, rides) {
        let map = new Map()
        //处理rides以end为key分组
        rides = rides.map((e, index) => {
          if (map.has(e[1])) {
            map.get(e[1]).push(index)
          } else {
            map.set(e[1], [index])
          }
          return [e[0], e[1] - e[0] + e[2]]
        })
        //动态规划数组
        let maxV = new Array(n + 1).fill(0)
        //对于每个点，我们遍历以它结尾的订单，即可得到到这个点最多可赚多少
        //i 代表当前结尾  遍历每个end为i的订单 start为该订单的起始点 value为该订单赚多少钱
        //maxV[end] = max(maxV[end],maxV[start]+value);
        for (let end = 1; end <= n; end++) {
          maxV[end] = maxV[end - 1]
          let endAtHere = map.has(end) ? map.get(end) : []
          for (let index of endAtHere) {
            let start = rides[index][0]
            let value = rides[index][1]
            maxV[end] = Math.max(maxV[end], maxV[start] + value)
          }
        }
        return maxV[n]
      }
      console.log(
        maxTaxiEarnings(5, [
          [2, 5, 4],
          [1, 5, 1]
        ])
      )
    </script>
  </body>
</html>
